package euler.p051_100;

import java.util.Stack;

import euler.MainEuler;
import euler.helper.NaturalHelper;

public class Euler092 extends MainEuler {

    /*
        A number chain is created by continuously adding
        the square of the digits in a number to form a
         new number until it has been seen before.

        For example,

        44 → 32 → 13 → 10 → 1 → 1
        85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

        Therefore any chain that arrives at 1 or 89
        will become stuck in an endless loop.
        What is most amazing is that EVERY starting number
        will eventually arrive at 1 or 89.

        How many starting numbers below ten million will arrive at 89?

     */
    public String resolve() {

        int limite = 10000000;

        int[] endChain = new int[NaturalHelper.cantidadDigitos(limite-1, 10) * (cuadrados[cuadrados.length-1]) + 1];
        endChain[1] = 1;
        endChain[89] = 89;

        for (int i = 1; i < endChain.length; i++) {
            if (endChain[i] == 0) {
                int n = i;

                Stack<Integer> s = new Stack<Integer>();

                while ((endChain[n] != 1) && (endChain[n] != 89)){
                    s.push(n);
                    n = next(n);
                }

                n = endChain[n];

                while (!s.isEmpty()) {
                    endChain[s.pop()] = n;
                }
            }
        }

        int count = 0;
        for (int i = 1; i < limite; i++) {
            if (endChain[next(i)] == 89) {
                count++;
            }
        }

        return String.valueOf(count);
        // 8581146
    }

    private static int[] cuadrados = {0,1,4,9,16,25,36,49,64,81};
    private static int next(int n) {
        int suma = 0;

        while (n > 0) {
            int d = n % 10;
            suma+=cuadrados[d];
            n/=10;
        }

        return suma;
    }

}
